{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways Where Square of Number Is Equal to Product of Two Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #math #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #数学 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numTriplets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数的平方等于两数乘积的方法数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数数组 <code>nums1</code> 和 <code>nums2</code> ，请你返回根据以下规则形成的三元组的数目（类型 1 和类型 2 ）：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>类型 1：三元组 <code>(i, j, k)</code> ，如果 <code>nums1[i]<sup>2</sup>&nbsp;== nums2[j] * nums2[k]</code> 其中 <code>0 &lt;= i &lt; nums1.length</code> 且 <code>0 &lt;= j &lt; k &lt; nums2.length</code></li>\n",
    "\t<li>类型 2：三元组 <code>(i, j, k)</code> ，如果 <code>nums2[i]<sup>2</sup>&nbsp;== nums1[j] * nums1[k]</code> 其中 <code>0 &lt;= i &lt; nums2.length</code> 且 <code>0 &lt;= j &lt; k &lt; nums1.length</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums1 = [7,4], nums2 = [5,2,8,9]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>类型 1：(1,1,2), nums1[1]^2 = nums2[1] * nums2[2] (4^2 = 2 * 8)</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums1 = [1,1], nums2 = [1,1,1]\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>所有三元组都符合题目要求，因为 1^2 = 1 * 1\n",
    "类型 1：(0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2), nums1[i]^2 = nums2[j] * nums2[k]\n",
    "类型 2：(0,0,1), (1,0,1), (2,0,1), nums2[i]^2 = nums1[j] * nums1[k]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums1 = [7,7,8,3], nums2 = [1,2,9,7]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>有两个符合题目要求的三元组\n",
    "类型 1：(3,0,2), nums1[3]^2 = nums2[0] * nums2[2]\n",
    "类型 2：(3,0,1), nums2[3]^2 = nums1[0] * nums1[1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>不存在符合题目要求的三元组\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums1.length, nums2.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 10^5</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-where-square-of-number-is-equal-to-product-of-two-numbers](https://leetcode.cn/problems/number-of-ways-where-square-of-number-is-equal-to-product-of-two-numbers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-where-square-of-number-is-equal-to-product-of-two-numbers](https://leetcode.cn/problems/number-of-ways-where-square-of-number-is-equal-to-product-of-two-numbers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,4]\\n[5,2,8,9]', '[1,1]\\n[1,1,1]', '[7,7,8,3]\\n[1,2,9,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        nums1.sort()\n",
    "        nums2.sort()\n",
    "        def total(x, y):\n",
    "            res = 0\n",
    "            for i in x:\n",
    "                m, n = 0, len(y)-1\n",
    "                tmp_sum = i ** 2\n",
    "                if y[m] * y[m] > tmp_sum:\n",
    "                    continue\n",
    "                if y[n] * y[n] < tmp_sum:\n",
    "                    break\n",
    "            \n",
    "                while m < n:\n",
    "                    if y[m] * y[n] < tmp_sum:\n",
    "                        m += 1\n",
    "                    elif y[m] * y[n] > tmp_sum:\n",
    "                        n -= 1\n",
    "                    else:\n",
    "                        if y[m] == y[n]:\n",
    "                            tmp = int((n - m + 1) * (n - m) / 2)\n",
    "                            res += tmp\n",
    "                            break\n",
    "                        else:\n",
    "                            j, k = m + 1, n - 1\n",
    "                            while y[j] == y[m]:\n",
    "                                j += 1\n",
    "                            while y[k] == y[n]:\n",
    "                                k -= 1\n",
    "                            \n",
    "                            res += (j-m) * (n-k)\n",
    "                            m = j\n",
    "                            n = k\n",
    "            return res\n",
    "            \n",
    "        return total(nums1, nums2) + total(nums2, nums1)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 分解因数法\n",
    "        def factor(n):\n",
    "            n *= n\n",
    "            for i in range(1, isqrt(n) + 1):\n",
    "                if n % i == 0:\n",
    "                    yield i, n // i\n",
    "\n",
    "        c1 = Counter(nums1)\n",
    "        c2 = Counter(nums2)\n",
    "        ans = 0\n",
    "\n",
    "        for n in c1:\n",
    "            for a, b in factor(n):\n",
    "                if a == b:\n",
    "                    ans += c1[n] * comb(c2[a], 2)\n",
    "                elif c2[a] > 0 and c2[b] > 0:\n",
    "                    ans += c1[n] * c2[a] * c2[b]\n",
    "\n",
    "        for n in c2:\n",
    "            for a, b in factor(n):\n",
    "                if a == b:\n",
    "                    ans += c2[n] * comb(c1[a], 2)\n",
    "                elif c1[a] > 0 and c1[b] > 0:\n",
    "                    ans += c2[n] * c1[a] * c1[b]\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pair(self,cnt1:dict,cnt2:dict)->int:\n",
    "        ans=0\n",
    "        for(x,a)in cnt1.items():\n",
    "            for(y,b)in cnt2.items():\n",
    "                if x*x%y==0 and x*x//y in cnt2.keys():\n",
    "                    if y==x*x//y:ans+=a*b*(b-1)//2\n",
    "                    elif y<x*x//y:ans+=a*b*cnt2[x*x//y]\n",
    "        return ans\n",
    "\n",
    "    def numTriplets(self,nums1:List[int],nums2:List[int])->int:\n",
    "        cnt1,cnt2=collections.Counter(nums1),collections.Counter(nums2)        \n",
    "        return self.pair(cnt1,cnt2)+self.pair(cnt2,cnt1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dict_nums1 = Counter(nums1)\n",
    "        dict_nums2 = Counter(nums2)\n",
    "        key_nums1 = sorted(dict_nums1)\n",
    "        key_nums2 = sorted(dict_nums2)\n",
    "\n",
    "        def get_count(sub_nums1, sub_nums2, d_nums1, d_nums2):\n",
    "            ans = 0\n",
    "            for num in sub_nums1:\n",
    "                power_num = num ** 2\n",
    "                for num2 in sub_nums2:\n",
    "                    if num2 <= num:\n",
    "                        if not power_num % num2:\n",
    "                            pair_num = power_num // num2\n",
    "                            if pair_num in d_nums2:\n",
    "                                if pair_num == num2:\n",
    "                                    if d_nums2[pair_num] > 1:\n",
    "                                        count_s = (d_nums2[pair_num] - 1) * d_nums2[pair_num] // 2\n",
    "                                        ans += d_nums1[num] * count_s\n",
    "                                else:\n",
    "                                    ans += d_nums1[num] * d_nums2[num2] * d_nums2[pair_num]\n",
    "                    else:\n",
    "                        break\n",
    "            return ans\n",
    "\n",
    "        count = get_count(key_nums1, key_nums2, dict_nums1, dict_nums2)\n",
    "        count2 = get_count(key_nums2, key_nums1, dict_nums2, dict_nums1)\n",
    "        return count + count2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        def getTriplets(map1: Counter, map2: Counter):\n",
    "            triplets = 0\n",
    "            for num1, count1 in map1.items():\n",
    "                square = num1 * num1\n",
    "                for num2, count2 in map2.items():\n",
    "                    if square % num2 == 0:\n",
    "                        num3 = square // num2\n",
    "                        if num2 == num3:\n",
    "                            curTriplets = count1 * count2 * (count2 - 1) // 2\n",
    "                            triplets += curTriplets\n",
    "                        elif num2 < num3 and num3 in map2:\n",
    "                            count3 = map2[num3]\n",
    "                            curTriplets = count1 * count2 * count3\n",
    "                            triplets += curTriplets\n",
    "            return triplets\n",
    "\n",
    "        map1 = collections.Counter(nums1)\n",
    "        map2 = collections.Counter(nums2)\n",
    "        return getTriplets(map1, map2) + getTriplets(map2, map1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dic1 = collections.Counter(nums1)\n",
    "        dic2 = collections.Counter(nums2)\n",
    "        def Triplets(dic1, dic2):\n",
    "            res = 0\n",
    "            for num1, count1 in dic1.items():\n",
    "                square = num1 ** 2\n",
    "                for num2, count2 in dic2.items():\n",
    "                    if square % num2 == 0:\n",
    "                        num3  = square // num2\n",
    "                        if num2 == num3:\n",
    "                            res += (count1 * (count2 - 1) * count2 // 2)\n",
    "                        elif num2 < num3 and num3 in dic2:\n",
    "                            res += (count1 * count2 * dic2[num3])\n",
    "        \n",
    "            return res\n",
    "        \n",
    "        return Triplets(dic1, dic2) + Triplets(dic2, dic1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        def getTriplets(map1: Counter, map2: Counter):\n",
    "            triplets = 0\n",
    "            for num1, count1 in map1.items():\n",
    "                square = num1 * num1\n",
    "                for num2, count2 in map2.items():\n",
    "                    if square % num2 == 0:\n",
    "                        num3 = square // num2\n",
    "                        triplets += count1 * count2 * (map2[num3] - (num2 == num3))\n",
    "\n",
    "            return triplets >> 1\n",
    "\n",
    "        map1 = collections.Counter(nums1)\n",
    "        map2 = collections.Counter(nums2)\n",
    "        return getTriplets(map1, map2) + getTriplets(map2, map1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        def getTriplets(map1: Counter, map2: Counter):\n",
    "            triplets = 0\n",
    "            for num1, count1 in map1.items():\n",
    "                square = num1 * num1\n",
    "                for num2, count2 in map2.items():\n",
    "                    if square % num2 == 0:\n",
    "                        num3 = square // num2\n",
    "                        if num2 == num3:\n",
    "                            curTriplets = count1 * count2 * (count2 - 1) // 2\n",
    "                            triplets += curTriplets\n",
    "                        elif num2 < num3 and num3 in map2:\n",
    "                            count3 = map2[num3]\n",
    "                            curTriplets = count1 * count2 * count3\n",
    "                            triplets += curTriplets\n",
    "            return triplets\n",
    "\n",
    "        map1 = collections.Counter(nums1)\n",
    "        map2 = collections.Counter(nums2)\n",
    "        return getTriplets(map1, map2) + getTriplets(map2, map1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        def getTriplets(map1: Counter, map2: Counter):\n",
    "            triplets = 0\n",
    "            for num1, count1 in map1.items():\n",
    "                square = num1 * num1\n",
    "                for num2, count2 in map2.items():\n",
    "                    if square % num2 == 0:\n",
    "                        num3 = square // num2\n",
    "                        if num2 == num3:\n",
    "                            triplets += count1 * comb(count2, 2)\n",
    "                        elif num2 < num3 and num3 in map2:\n",
    "                            triplets += count1 * count2 * map2[num3]\n",
    "            return triplets\n",
    "\n",
    "        map1 = collections.Counter(nums1)\n",
    "        map2 = collections.Counter(nums2)\n",
    "        return getTriplets(map1, map2) + getTriplets(map2, map1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        def getTriplets(map1: Counter, map2: Counter):\n",
    "            triplets = 0\n",
    "            for num1, count1 in map1.items():\n",
    "                square = num1 * num1\n",
    "                for num2, count2 in map2.items():\n",
    "                    if square % num2 == 0:\n",
    "                        num3 = square // num2\n",
    "                        if num2 == num3:\n",
    "                            curTriplets = count1 * count2 * (count2 - 1) // 2\n",
    "                            triplets += curTriplets\n",
    "                        elif num2 < num3 and num3 in map2:\n",
    "                            count3 = map2[num3]\n",
    "                            curTriplets = count1 * count2 * count3\n",
    "                            triplets += curTriplets\n",
    "            return triplets\n",
    "\n",
    "        map1 = collections.Counter(nums1)\n",
    "        map2 = collections.Counter(nums2)\n",
    "        return getTriplets(map1, map2) + getTriplets(map2, map1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        res = 0\n",
    "        for num1 in nums1:\n",
    "            d = {}\n",
    "            tmp = num1**2\n",
    "            for num2 in nums2:\n",
    "                if tmp % num2 == 0:\n",
    "                    t = tmp//num2\n",
    "                    if t in d:\n",
    "                        res += d[t]\n",
    "                if num2 in d:\n",
    "                    d[num2] += 1\n",
    "                else:\n",
    "                    d[num2] = 1\n",
    "        \n",
    "        for num2 in nums2:\n",
    "            d = {}\n",
    "            tmp = num2**2\n",
    "            for num1 in nums1:\n",
    "                if tmp % num1 == 0:\n",
    "                    t = tmp//num1\n",
    "                    if t in d:\n",
    "                        res += d[t]\n",
    "                if num1 in d:\n",
    "                    d[num1] += 1\n",
    "                else:\n",
    "                    d[num1] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        def getTriplets(map1:Counter,map2:Counter):\n",
    "            triplets=0\n",
    "            for num1,count1 in map1.items():\n",
    "                square=num1*num1\n",
    "                for num2,count2 in map2.items():\n",
    "                    if square%num2==0:\n",
    "                        num3=square//num2\n",
    "                        if num2==num3:\n",
    "                            curTriplets=count1*count2*(count2-1)//2\n",
    "                            triplets+=curTriplets\n",
    "                        elif num2>num3 and num3 in map2:\n",
    "                            count3=map2[num3]\n",
    "                            curTriplets=count1*count2*count3\n",
    "                            triplets+=curTriplets\n",
    "            return triplets\n",
    "        \n",
    "        map1=collections.Counter(nums1)\n",
    "        map2=collections.Counter(nums2)\n",
    "        return getTriplets(map1,map2)+getTriplets(map2,map1)\n",
    "        \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        def hp(nums1, nums2):\n",
    "            cnts1 = collections.Counter([n * n for n in nums1])\n",
    "\n",
    "            ans = 0\n",
    "            mp = collections.defaultdict(int)\n",
    "\n",
    "            for n in nums2:\n",
    "                for k in cnts1.keys():\n",
    "                    if k % n == 0 and k // n in mp:\n",
    "                        ans += mp[k // n] * cnts1[k]\n",
    "\n",
    "                mp[n] += 1\n",
    "\n",
    "            return ans \n",
    "\n",
    "        return hp(nums1, nums2) + hp(nums2, nums1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        c2 = Counter(nums2)\n",
    "        for x, y in combinations(nums1, 2):\n",
    "            if (a := isqrt(x * y)) ** 2 == x * y:\n",
    "                ans += c2[a]\n",
    "        c1 = Counter(nums1)\n",
    "        for x, y in combinations(nums2, 2):\n",
    "            if (a := isqrt(x * y)) ** 2 == x * y:\n",
    "                ans += c1[a]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        len1,len2,c=len(nums1),len(nums2),0\n",
    "        cn1=collections.Counter(i*i for i in nums1)\n",
    "        cn2=collections.Counter(i*i for i in nums2)\n",
    "        for i in range(len1):\n",
    "            for j in range(i+1,len1):\n",
    "                if nums1[i]*nums1[j] in cn2:\n",
    "                    c+=cn2[nums1[i]*nums1[j]]\n",
    "        for i in range(len2):\n",
    "            for j in range(i+1,len2):\n",
    "                if nums2[i]*nums2[j] in cn1:\n",
    "                    c+=cn1[nums2[i]*nums2[j]]\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        def getTriplets(map1: Counter, map2: Counter):\n",
    "            triplets = 0\n",
    "            for num1, count1 in map1.items():\n",
    "                square = num1 * num1\n",
    "                for num2, count2 in map2.items():\n",
    "                    if square % num2 == 0:\n",
    "                        num3 = square // num2\n",
    "                        if num2 == num3:\n",
    "                            triplets += count1 * count2 * (count2 - 1)\n",
    "                        elif num3 in map2:\n",
    "                            triplets += count1 * count2 * map2[num3]\n",
    "            return triplets // 2\n",
    "\n",
    "        map1 = collections.Counter(nums1)\n",
    "        map2 = collections.Counter(nums2)\n",
    "        return getTriplets(map1, map2) + getTriplets(map2, map1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        def getTriplets(map1: Counter, map2: Counter):\n",
    "            triplets = 0\n",
    "            for num1, count1 in map1.items():\n",
    "                square = num1 * num1\n",
    "                for num2, count2 in map2.items():\n",
    "                    if square % num2 == 0:\n",
    "                        num3 = square // num2\n",
    "                        if num2 == num3:\n",
    "                            curTriplets = count1 * count2 * (count2 - 1) // 2\n",
    "                            triplets += curTriplets\n",
    "                        elif num2 < num3 and num3 in map2:\n",
    "                            count3 = map2[num3]\n",
    "                            curTriplets = count1 * count2 * count3\n",
    "                            triplets += curTriplets\n",
    "            return triplets\n",
    "\n",
    "        map1 = collections.Counter(nums1)\n",
    "        map2 = collections.Counter(nums2)\n",
    "        return getTriplets(map1, map2) + getTriplets(map2, map1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dic1 = Counter([i**2 for i in nums1])\n",
    "        dic2 = Counter([i**2 for i in nums2])\n",
    "        \n",
    "        n = len(nums1)\n",
    "        m = len(nums2)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                ans += dic2.get(nums1[i] * nums1[j], 0)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(i):\n",
    "                ans += dic1.get(nums2[i] * nums2[j], 0)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        def getTriplets(map1: Counter, map2: Counter):\n",
    "            triplets = 0\n",
    "            for num1, count1 in map1.items():\n",
    "                square = num1 * num1\n",
    "                for num2, count2 in map2.items():\n",
    "                    if not square % num2:\n",
    "                        num3 = square // num2\n",
    "                        triplets += count1 * count2 * (map2[num3] - (num2 == num3))\n",
    "\n",
    "            return triplets >> 1\n",
    "\n",
    "        map1 = collections.Counter(nums1)\n",
    "        map2 = collections.Counter(nums2)\n",
    "        return getTriplets(map1, map2) + getTriplets(map2, map1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        len1, len2, c = len(nums1), len(nums2), 0\n",
    "        cn1 = collections.Counter(i * i for i in nums1)\n",
    "        cn2 = collections.Counter(i * i for i in nums2)\n",
    "        for i in range(len1):\n",
    "            for j in range(i+1, len1):\n",
    "                if nums1[i] * nums1[j] in cn2:\n",
    "                    c += cn2[nums1[i] * nums1[j]]\n",
    "        for i in range(len2):\n",
    "            for j in range(i+1, len2):\n",
    "                if nums2[i] * nums2[j] in cn1:\n",
    "                    c += cn1[nums2[i] * nums2[j]]\n",
    "        return c\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        cnt1, cnt2 = Counter(nums1), Counter(nums2)\n",
    "\n",
    "        def f(a, b):\n",
    "            res = 0\n",
    "            for k, v in a.items():\n",
    "                for kk, vv in b.items():\n",
    "                    if k == kk:\n",
    "                        res += v * comb(vv, 2)\n",
    "                    else:\n",
    "                        if k ** 2 % kk == 0:\n",
    "                            res += v * vv * b[k ** 2 // kk] / 2\n",
    "            return res \n",
    "        \n",
    "        return int(f(cnt1, cnt2) + f(cnt2, cnt1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        nums1.sort()\n",
    "        nums2.sort()\n",
    "        def getTriplets(map1:List[int],map2:List[int])->int:\n",
    "            count = 0\n",
    "            for i in range(len(map1)):\n",
    "                qrt = map1[i]**2\n",
    "                left,right = 0,len(map2)-1\n",
    "                while left<right:\n",
    "                    qrt1 = map2[left]*map2[right]\n",
    "                    if qrt1==qrt:\n",
    "                        if map2[left]==map2[right]:\n",
    "                            k = right-left+1\n",
    "                            count+=k*(k-1)//2\n",
    "                            break\n",
    "                        else:\n",
    "                            left_same=0\n",
    "                            while left+1<right and map2[left]==map2[left+1]:\n",
    "                                left+=1\n",
    "                                left_same+=1\n",
    "                            right_same=0\n",
    "                            while right-1>left and map2[right]==map2[right-1]:\n",
    "                                right-=1\n",
    "                                right_same+=1\n",
    "                            count+=(left_same+1)*(right_same+1)\n",
    "                            left+=1\n",
    "                            right-=1\n",
    "                    else:\n",
    "                        if qrt1>qrt:\n",
    "                            right-=1\n",
    "                        else:\n",
    "                            left+=1\n",
    "            return count\n",
    "        return getTriplets(nums1,nums2)+getTriplets(nums2,nums1)\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        res = 0\n",
    "        nums1_dic = dict()\n",
    "        nums2_dic = dict()\n",
    "        if n1 == n2 == 1:\n",
    "            return res\n",
    "        for x in nums1:\n",
    "            if x in nums1_dic:\n",
    "                res += nums1_dic[x]\n",
    "            else:\n",
    "                tmp = 0\n",
    "                for i in range(n2-1):\n",
    "                    if (x**2) % nums2[i] == 0:\n",
    "                        for j in range(i+1, n2):\n",
    "                            if (nums2[j]*nums2[i]) == (x**2):\n",
    "                                tmp += 1\n",
    "                nums1_dic[x] = tmp\n",
    "                res += tmp\n",
    "        for y in nums2:\n",
    "            if y in nums2_dic:\n",
    "                res += nums2_dic[y]\n",
    "            else:\n",
    "                tmp = 0\n",
    "                for i in range(n1-1):\n",
    "                    if (y**2) % nums1[i] == 0:\n",
    "                        for j in range(i+1, n1):\n",
    "                            if (nums1[i]*nums1[j]) == (y**2):\n",
    "                                tmp += 1\n",
    "                nums2_dic[y] = tmp\n",
    "                res += tmp\n",
    "        print(nums2_dic)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        table = {}\n",
    "        n1 = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        table = defaultdict(int)\n",
    "        table2 = defaultdict(int)\n",
    "        ans = 0\n",
    "        for i in range(n1):\n",
    "            table[nums1[i]**2] += 1\n",
    "        for i in range(n2-1):\n",
    "            for j in range(i+1,n2):\n",
    "                if nums2[i]*nums2[j] in table:\n",
    "                    ans += table[nums2[i]*nums2[j]]\n",
    "        print(ans)\n",
    "        for i in range(n2):\n",
    "            table2[nums2[i]**2] += 1\n",
    "        for i in range(n1-1):\n",
    "            for j in range(i+1,n1):\n",
    "                if nums1[i]*nums1[j] in table2:\n",
    "                    ans += table2[nums1[i]*nums1[j]]\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        res = 0\n",
    "        nums2.sort()\n",
    "        nums1.sort()\n",
    "        unordered_map1 = dict()\n",
    "        unordered_map2 = dict()\n",
    "        for num in nums2:\n",
    "            if unordered_map2.get(num):\n",
    "                unordered_map2[num] += 1\n",
    "            else:\n",
    "                unordered_map2[num] = 1\n",
    "\n",
    "        for num in nums1:\n",
    "            left,right = 0,len(nums2)-1\n",
    "            while left<right:\n",
    "                cur = nums2[left] * nums2[right]\n",
    "                if cur==num*num:\n",
    "                    if nums2[left] != nums2[right]:\n",
    "                        res += unordered_map2[nums2[left]] * unordered_map2[nums2[right]]\n",
    "                    else:\n",
    "                        res += unordered_map2[nums2[left]] * (unordered_map2[nums2[left]] - 1) // 2\n",
    "                    left += 1\n",
    "                    while left<right and nums2[left]==nums2[left-1]:\n",
    "                        left += 1\n",
    "                elif cur>num*num:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    left += 1\n",
    "\n",
    "\n",
    "        for num in nums1:\n",
    "            if unordered_map1.get(num):\n",
    "                unordered_map1[num] += 1\n",
    "            else:\n",
    "                unordered_map1[num] = 1\n",
    "\n",
    "        for num in nums2:\n",
    "            left,right = 0,len(nums1)-1\n",
    "            while left<right:\n",
    "                cur = nums1[left] * nums1[right]\n",
    "                if cur==num*num:\n",
    "                    if nums1[left] != nums1[right]:\n",
    "                        res += unordered_map1[nums1[left]] * unordered_map1[nums1[right]]\n",
    "                    else:\n",
    "                        res += unordered_map1[nums1[left]] * (unordered_map1[nums1[left]] - 1) // 2\n",
    "                    left += 1\n",
    "                    while left<right and nums1[left]==nums1[left-1]:\n",
    "                        left += 1\n",
    "                elif cur>num*num:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    left += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\r\n",
    "        nums1.sort()\r\n",
    "        nums2.sort()\r\n",
    "        nums1_counter, nums2_counter = collections.Counter(nums1), collections.Counter(nums2)\r\n",
    "        return self.helper(nums1_counter, nums2_counter) + self.helper(nums2_counter, nums1_counter)\r\n",
    "    \r\n",
    "    def helper(self, arr1_counter, arr2_counter):\r\n",
    "        res = 0\r\n",
    "        arr2 = list(arr2_counter.keys())\r\n",
    "        for num in arr1_counter:\r\n",
    "            # 如果arr2中所有元素相同\r\n",
    "            if len(arr2_counter) == 1 and (a := arr2_counter[arr2[0]]) > 1 and arr2[0] ** 2 == num:\r\n",
    "                res += math.comb(a, 2) * arr1_counter[num]\r\n",
    "                continue\r\n",
    "            # 如果arr1[i]在arr2中不止一个 \r\n",
    "            if num in arr2 and arr2_counter[num] > 1:\r\n",
    "                res += math.comb(arr2_counter[num], 2) * arr1_counter[num]\r\n",
    "            count = 0\r\n",
    "            s, e = 0, len(arr2) - 1\r\n",
    "            while s < e:\r\n",
    "                if num ** 2 == arr2[s] * arr2[e]:\r\n",
    "                    count += arr2_counter[arr2[s]] * arr2_counter[arr2[e]]\r\n",
    "                    s, e = s + 1, e - 1\r\n",
    "                elif num ** 2 > arr2[s] * arr2[e]:\r\n",
    "                    s += 1\r\n",
    "                else:\r\n",
    "                    e -= 1\r\n",
    "            res += count * arr1_counter[num]\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        def getTriplets(a1, a2):\n",
    "            st1 = Counter([x ** 2 for x in a1])\n",
    "            st2 = Counter(a2)\n",
    "            ans = 0\n",
    "            print(f'{st1, st2}')\n",
    "            for k1, v1 in st1.items():\n",
    "                for k2, v2 in st2.items():\n",
    "                    k3 = k1 // k2\n",
    "                    if k3 * k2 == k1 and k3 in st2:\n",
    "                        if k3 == k2:\n",
    "                            ans += v1 * st2[k2] * (st2[k3] - 1)\n",
    "                        else:\n",
    "                            ans += v1 * st2[k2] * st2[k3]\n",
    "            return ans // 2\n",
    "        return getTriplets(nums1, nums2) + getTriplets(nums2, nums1)\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        nums1 = Counter(nums1)\n",
    "        nums2 = Counter(nums2)\n",
    "        print(nums1, nums2)\n",
    "        res = 0\n",
    "        for i in nums1:\n",
    "            left = 0\n",
    "            right = len(nums2) - 1\n",
    "            nums2_keys = sorted(nums2.keys())\n",
    "            while left < right:\n",
    "                if (a := i ** 2) == (b := nums2_keys[left] * nums2_keys[right]):\n",
    "                    res += nums1[i] * nums2[nums2_keys[left]] * nums2[nums2_keys[right]]\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "                elif a > b:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "            if left == right and i ** 2 == nums2_keys[left] * nums2_keys[right]:\n",
    "                res += nums1[i] * (a := nums2[nums2_keys[left]]) * (a - 1) // 2\n",
    "        for i in nums2:\n",
    "            left = 0\n",
    "            right = len(nums1) - 1\n",
    "            nums1_keys = sorted(nums1.keys())\n",
    "            while left < right:\n",
    "                if (a := i ** 2) == (b := nums1_keys[left] * nums1_keys[right]):\n",
    "                    res += nums2[i] * nums1[nums1_keys[left]] * nums1[nums1_keys[right]]\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "                elif a > b:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "            if left == right and i ** 2 == nums1_keys[left] * nums1_keys[right]:\n",
    "                res += nums2[i] * (a := nums1[nums1_keys[left]]) * (a - 1) // 2\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mapping1 = {}\n",
    "        square1 = {}\n",
    "        for num1 in nums1:\n",
    "            if(num1 not in mapping1):\n",
    "                mapping1[num1] = 1\n",
    "                square1[num1**2] = 1\n",
    "            else:\n",
    "                mapping1[num1] += 1\n",
    "                square1[num1**2] += 1\n",
    "        mapping2 = {}\n",
    "        square2 = {}\n",
    "        for num2 in nums2:\n",
    "            if(num2 not in mapping2):\n",
    "                mapping2[num2] = 1\n",
    "                square2[num2**2] = 1\n",
    "            else:\n",
    "                mapping2[num2] += 1\n",
    "                square2[num2**2] += 1\n",
    "        keys1 = sorted(list(mapping1.keys()))\n",
    "        keys2 = sorted(list(mapping2.keys()))\n",
    "        result = 0\n",
    "\n",
    "        for j in range(len(keys2)):\n",
    "            for k in range(j,len(keys2)):\n",
    "                if(j == k):\n",
    "                    if(keys2[j]*keys2[k] in square1):\n",
    "                        result += mapping2[keys2[j]]*(mapping2[keys2[k]]-1)//2*square1[keys2[j]*keys2[k]]\n",
    "                else:\n",
    "                    if(keys2[j]*keys2[k] in square1):\n",
    "                        result += mapping2[keys2[j]]*mapping2[keys2[k]]*square1[keys2[j]*keys2[k]]\n",
    "                    \n",
    "        for j in range(len(keys1)):\n",
    "            for k in range(j,len(keys1)):\n",
    "                if(j == k):\n",
    "                    if(keys1[j]*keys1[k] in square2):\n",
    "                        result += mapping1[keys1[j]]*(mapping1[keys1[k]]-1)//2*square2[keys1[j]*keys1[k]]\n",
    "                else:\n",
    "                    if(keys1[j]*keys1[k] in square2):\n",
    "                        result += mapping1[keys1[j]]*mapping1[keys1[k]]*square2[keys1[j]*keys1[k]]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dict_nums1 = Counter(nums1)\n",
    "        dict_nums2 = Counter(nums2)\n",
    "        key_nums1 = sorted(dict_nums1)\n",
    "        key_nums2 = sorted(dict_nums2)\n",
    "\n",
    "        def get_count(sub_nums1, sub_nums2, d_nums1, d_nums2):\n",
    "            ans = 0\n",
    "            for num in sub_nums1:\n",
    "                power_num = num ** 2\n",
    "                for num2 in sub_nums2:\n",
    "                    if num2 <= num:\n",
    "                        if not power_num % num2:\n",
    "                            pair_num = power_num // num2\n",
    "                            if pair_num in d_nums2:\n",
    "                                if pair_num == num2:\n",
    "                                    if d_nums2[pair_num] > 1:\n",
    "                                        count_s = (d_nums2[pair_num] - 1) * d_nums2[pair_num] // 2\n",
    "                                        ans += d_nums1[num] * count_s\n",
    "                                else:\n",
    "                                    ans += d_nums1[num] * d_nums2[num2] * d_nums2[pair_num]\n",
    "                    else:\n",
    "                        break\n",
    "            return ans\n",
    "\n",
    "        count = get_count(key_nums1, key_nums2, dict_nums1, dict_nums2)\n",
    "        count2 = get_count(key_nums2, key_nums1, dict_nums2, dict_nums1)\n",
    "        return count + count2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mapping1 = {}\n",
    "        square1 = {}\n",
    "        for num1 in nums1:\n",
    "            if(num1 not in mapping1):\n",
    "                mapping1[num1] = 1\n",
    "                square1[num1**2] = 1\n",
    "            else:\n",
    "                mapping1[num1] += 1\n",
    "                square1[num1**2] += 1\n",
    "        mapping2 = {}\n",
    "        square2 = {}\n",
    "        for num2 in nums2:\n",
    "            if(num2 not in mapping2):\n",
    "                mapping2[num2] = 1\n",
    "                square2[num2**2] = 1\n",
    "            else:\n",
    "                mapping2[num2] += 1\n",
    "                square2[num2**2] += 1\n",
    "        keys1 = sorted(list(mapping1.keys()))\n",
    "        keys2 = sorted(list(mapping2.keys()))\n",
    "        result = 0\n",
    "\n",
    "        for j in range(len(keys2)):\n",
    "            for k in range(j,len(keys2)):\n",
    "                if(j == k):\n",
    "                    if(keys2[j]*keys2[k] in square1):\n",
    "                        result += mapping2[keys2[j]]*(mapping2[keys2[k]]-1)//2*square1[keys2[j]*keys2[k]]\n",
    "                else:\n",
    "                    if(keys2[j]*keys2[k] in square1):\n",
    "                        result += mapping2[keys2[j]]*mapping2[keys2[k]]*square1[keys2[j]*keys2[k]]\n",
    "                    \n",
    "        for j in range(len(keys1)):\n",
    "            for k in range(j,len(keys1)):\n",
    "                if(j == k):\n",
    "                    if(keys1[j]*keys1[k] in square2):\n",
    "                        result += mapping1[keys1[j]]*(mapping1[keys1[k]]-1)//2*square2[keys1[j]*keys1[k]]\n",
    "                else:\n",
    "                    if(keys1[j]*keys1[k] in square2):\n",
    "                        result += mapping1[keys1[j]]*mapping1[keys1[k]]*square2[keys1[j]*keys1[k]]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mapping1 = {}\n",
    "        square1 = {}\n",
    "        for num1 in nums1:\n",
    "            if(num1 not in mapping1):\n",
    "                mapping1[num1] = 1\n",
    "                square1[num1**2] = 1\n",
    "            else:\n",
    "                mapping1[num1] += 1\n",
    "                square1[num1**2] += 1\n",
    "        mapping2 = {}\n",
    "        square2 = {}\n",
    "        for num2 in nums2:\n",
    "            if(num2 not in mapping2):\n",
    "                mapping2[num2] = 1\n",
    "                square2[num2**2] = 1\n",
    "            else:\n",
    "                mapping2[num2] += 1\n",
    "                square2[num2**2] += 1\n",
    "        keys1 = sorted(list(mapping1.keys()))\n",
    "        keys2 = sorted(list(mapping2.keys()))\n",
    "        result = 0\n",
    "\n",
    "        for j in range(len(keys2)):\n",
    "            for k in range(j,len(keys2)):\n",
    "                if(j == k):\n",
    "                    if(keys2[j]*keys2[k] in square1):\n",
    "                        result += mapping2[keys2[j]]*(mapping2[keys2[k]]-1)//2*square1[keys2[j]*keys2[k]]\n",
    "                else:\n",
    "                    if(keys2[j]*keys2[k] in square1):\n",
    "                        result += mapping2[keys2[j]]*mapping2[keys2[k]]*square1[keys2[j]*keys2[k]]\n",
    "                    \n",
    "        for j in range(len(keys1)):\n",
    "            for k in range(j,len(keys1)):\n",
    "                if(j == k):\n",
    "                    if(keys1[j]*keys1[k] in square2):\n",
    "                        result += mapping1[keys1[j]]*(mapping1[keys1[k]]-1)//2*square2[keys1[j]*keys1[k]]\n",
    "                else:\n",
    "                    if(keys1[j]*keys1[k] in square2):\n",
    "                        result += mapping1[keys1[j]]*mapping1[keys1[k]]*square2[keys1[j]*keys1[k]]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cnt1, cnt2 = list(Counter(nums1).items()), list(Counter(nums2).items())\n",
    "        cntSquare1, cntSquare2 = Counter([x**2 for x in nums1]), Counter([x**2 for x in nums2])\n",
    "        print(cnt1, cnt2, cntSquare1, cntSquare2)\n",
    "        for i in range(len(cnt1)):\n",
    "            for j in range(i+1, len(cnt1)):\n",
    "                ans += cnt1[i][1] * cnt1[j][1] * cntSquare2[cnt1[i][0] * cnt1[j][0]]\n",
    "        for k, v in cnt1:\n",
    "            ans += v*(v-1)//2 * cntSquare2[k**2] \n",
    "        for i in range(len(cnt2)):\n",
    "            for j in range(i+1, len(cnt2)):\n",
    "                ans += cnt2[i][1] * cnt2[j][1] * cntSquare1[cnt2[i][0] * cnt2[j][0]]\n",
    "        for k, v in cnt2:\n",
    "            ans += v*(v-1)//2 * cntSquare1[k**2] \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        ans = 0\n",
    "\n",
    "        b = {}\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                k = (nums2[i]*nums2[j])**0.5\n",
    "                if k == int(k):\n",
    "                    print(nums2[i],nums2[j],k)\n",
    "                    k = int(k)\n",
    "                    if k in b:\n",
    "                        b[k] += 1\n",
    "                    else:\n",
    "                        b[k] = 1\n",
    "        \n",
    "        for num in nums1:\n",
    "            if num in b:\n",
    "                ans += b[num]\n",
    "        \n",
    "        b = {}\n",
    "        for i in range(m-1):\n",
    "            for j in range(i+1,m):\n",
    "                k = (nums1[i]*nums1[j])**0.5\n",
    "                if k == int(k):\n",
    "                    print(nums1[i],nums1[j],k)\n",
    "                    k = int(k)\n",
    "                    if k in b:\n",
    "                        b[k] += 1\n",
    "                    else:\n",
    "                        b[k] = 1\n",
    "\n",
    "        for num in nums2:\n",
    "            if num in b:\n",
    "                ans += b[num]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        nums1.sort()\n",
    "        nums2.sort()\n",
    "\n",
    "        print(nums1,nums2)\n",
    "        # first compos\n",
    "        count = 0\n",
    "\n",
    "        \n",
    "        for i in range(len(nums1)):\n",
    "            qrt = nums1[i]**2\n",
    "            left,right = 0,len(nums2)-1\n",
    "            while left<right:\n",
    "                qrt1 = nums2[left]*nums2[right]\n",
    "                if qrt1==qrt:\n",
    "                    if nums2[left]==nums2[right]:\n",
    "                        k = right-left+1\n",
    "                        count+=k*(k-1)//2\n",
    "                        break\n",
    "                    else:\n",
    "                        left_same=1\n",
    "                        while left+1<right and nums2[left]==nums2[left+1]:\n",
    "                            left+=1\n",
    "                            left_same+=1\n",
    "                        right_same=1\n",
    "                        while right-1>left and nums2[right]==nums2[right-1]:\n",
    "                            right-=1\n",
    "                            right_same+=1\n",
    "                        count+=left_same*right_same\n",
    "                        print(i,left_same,right_same,count,left,right)\n",
    "                        if left_same==1 and right_same==1:\n",
    "                            left+=1\n",
    "                            right-=1\n",
    "                        else:\n",
    "                            if left_same!=1:\n",
    "                                left+=1\n",
    "                            if right_same!=1:\n",
    "                                right-=1\n",
    "                else:\n",
    "                    if qrt1>qrt:\n",
    "                        right-=1\n",
    "                    else:\n",
    "                        left+=1\n",
    "        for i in range(len(nums2)):\n",
    "            qrt = nums2[i]**2\n",
    "            left,right = 0,len(nums1)-1\n",
    "            while left<right:\n",
    "                qrt1 = nums1[left]*nums1[right]\n",
    "                if qrt1==qrt:\n",
    "                    if nums1[left]==nums1[right]:\n",
    "                        k = right-left+1\n",
    "                        count+=k*(k-1)//2\n",
    "                        break\n",
    "                    else:\n",
    "                        left_same = 1\n",
    "                        while left+1<right and nums1[left]==nums1[left+1]:\n",
    "                            left+=1\n",
    "                            left_same+=1\n",
    "                        right_same=1\n",
    "                        while right-1>left and nums1[right]==nums1[right-1]:\n",
    "                            right-=1\n",
    "                            right_same+=1\n",
    "                        count+=left_same*right_same\n",
    "                        print(i,left_same,right_same,count,left,right)\n",
    "                        if left_same==1 and right_same==1:\n",
    "                            left+=1\n",
    "                            right-=1\n",
    "                        else:\n",
    "                            if left_same!=1:\n",
    "                                left+=1\n",
    "                            if right_same!=1:\n",
    "                                right-=1\n",
    "                    \n",
    "                else:\n",
    "                    if qrt1>qrt:\n",
    "                        right-=1\n",
    "                    else:\n",
    "                        left+=1\n",
    "        return count\n",
    "        \n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
